1710. Maximum Units on a Truck
Easy

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

  • numberOfBoxesi is the number of boxes of type i.
  • numberOfUnitsPerBoxi is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

 

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

 

Constraints:

  • 1 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106
Accepted
47,224
Submissions
66,267
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
If we have space for at least one box, it's always optimal to put the box with the most units.
Show Hint 2
Sort the box types with the number of units per box non-increasingly.
Show Hint 3
Iterate on the box types and take from each type as many as you can.

Average Rating: 4.42 (12 votes)

Premium

Solution


Overview

We have to fill the truck with any box type and try to fill in the maximum number of units. The 2D array boxTypes has the following information on each type of box,

  • Number of boxes of that type.
  • Number of units inside each box of that type.

We must choose the boxes which give us maximum units.

The problem can be implemented using Greedy Approach. We could iteratively fill the truck by picking up the boxes having maximum units from the remaining boxes at every point. Let's look at the approach to implement the problem.


Approach 1: Brute Force

Intuition

We must fill the truck with maximum units. Given the 2D array boxTypes, we could simply traverse over each box type, find the one with maximum units and fill the truck with all the boxes of that type. Once we fill the truck with a box type, we could mark it as used, and again find the box type with maximum units from the remaining ones. This would continue until the truck is not full.

Let the box type with maximum unit be maxUnitsBoxType. The number of boxes that can be put in the truck using boxes of type maxUnitsBoxType is given by maxUnitsBoxType[0].

However, we can only fill the truck until it is not full. That is, we could only put the boxes in the truck until the remaining truck size is greater than 00. Thus, if the remaining space is truck at a certain point is given by, remainingTruckSize, the number of boxes that can be put in the truck can be given by,

 boxCount =  min(maxUnitsBoxType[0], remainingTruckSize)

img

Let's understand how can we implement the above idea.

Algorithm

  • Initially, the truck is empty, hence the remaining truck capacity that must be filled would be equal to the truck size. Initialise variable remainingTruckSize to truckSize.

  • The truck will be filled with boxes one by one until it is not full. In every iteration, we must find a box with maximum units from the remaining box types. Let's use the method findMaxUnitBox that would return the index of a box type with maximum units given by maxUnitBoxIndex in the 2D array boxTypes\text{boxTypes}.

  • Once, we have the maxUnitBoxIndex, we could find the number of boxes that we could put in the truck as a minimum of remainingTruckSize and the number of boxes available of a given type. Calculate the total number of units and reduce the truck's remaining capacity based on the number of boxes put in the truck.

  • Also, we must mark the current box as used. One way of doing this would be to simply mark the number of units as -1. When findMaxUnitBox would indicate that all the boxes are already used and we must terminate.

  • The process of filling the truck with box types would continue until the truck is not full i.e remainingTruckSize is greater than 00.

Implementation

Complexity Analysis

  • Time Complexity : O(n2)\mathcal{O}(n^{2}), where nn is the number of elements in array boxTypes. In the method findMaxUnitBox, we are iterating over all the elements in array boxTypes to find the maximum units. In the worst case, when all the boxes are added to the truck we would iterate n times over the array of size n. This would give total time complexity as O(n2)\mathcal{O}(n^{2}).

  • Space Complexity: O(1)\mathcal{O}(1), as we are using constant extra space to maintain the variables remainingTruckSize and unitCount.


Approach 2: Using Array Sort

We could simplify the process of finding the maximum units in every iteration. We could arrange the box types in a particular order such that we could get the desired box type in constant time without having to iterate over the entire array. The simple way to implement this is to sort the array boxTypes in decreasing order of a number of units.

Once all the elements in array boxTypes are sorted in that order, we know that box type at 0th0^{th} position is the one with maximum units and the one at 1st1^{st} position having the second highest number of units and so on.

Algorithm

  • Initially, the truck is empty, hence the remaining truck capacity that must be filled would be equal to the truck size. Initialise variable remainingTruckSize to truckSize.

  • Sort the array boxTypes in decreasing order of a number of units.

  • Start picking up each box type from boxTypes array starting from 0th0^{th} position. The number of boxes that can be put in the truck would be the minimum of remainingTruckSize and the number of boxes available of the given type. Calculate the total number of units and reduce the truck's remaining capacity based on the number of boxes put in the truck.

  • The process of filling the truck with box types would continue until the truck is not full i.e remainingTruckSize is greater than 00.

The following figure illustrates the approach in detail for truckSize = 8 and boxTypes = [[3, 10], [6, 5], [4, 7], [2, 9]]

img

Implementation

Complexity Analysis

  • Time Complexity : O(nlogn)\mathcal{O}(n \log n), where n is the number of elements in array boxTypes.

    Sorting the array boxTypes of size n takes (nlogn)(n \log n) time. Post that, we iterate over each element in array boxTypes and in worst case, we might end up iterating over all the elements in the array. This gives us time complexity as O(nlogn)+O(n)=O(nlogn)\mathcal{O}(n \log n) + \mathcal{O}(n) = \mathcal{O}(n \log n).

  • Space Complexity: O(1)\mathcal{O}(1), as we use constant extra space.


Approach 3: Using Priority Queue

Intuition

There is yet another way to get the maximum units in constant time by using the Heap data structure. We could build Max Heap where the value at the root node of the heap is always the maximum value among all its children. So we could build a max heap based on the number of units.

In every iteration, we could pick up the box type which is at the root node, and remove it. After removing the root node, the next node with maximum units would become the root bode.

This approach is not an optimization over Approach 2 but just another way to solve the problem.

Algorithm

  • The heap data structure can be implemented using the priority queue. We must specify that the sort order must be based on the number of units in descending order.

  • Initially, the truck is empty, hence the remaining truck capacity that must be filled would be equal to the truck size. Initialise variable remainingTruckSize to truckSize.

  • The element at the top of the queue is the one having maximum units. Pick that element and remove it from the queue.

  • The number of boxes that can be put in the truck would be the minimum of remainingTruckSize and the number of boxes available of a given type. Calculate the total number of units and reduce the truck's remaining capacity based on the number of boxes put in the truck.

  • The process of filling the truck with box types would continue until the truck is not full i.e remainingTruckSize is greater than 00.

Implementation

Complexity Analysis

  • Time Complexity : O(nlogn)\mathcal{O}(n \log n), where nn is the number of elements in array boxTypes.

    We are adding all the elements of the array boxTypes in the priority queue, which takes O(n)\mathcal{O}(n) time.

    Post that, we would continue iteration until queue is not empty or remaining truck size is greater than 00. In worst case, we might end up iterating nn times. Also, removing elements from queue would take (logn)(\log n) time. This gives us time complexity as O(nlogn)+O(n)=O(nlogn)\mathcal{O}(n \log n) + \mathcal{O}(n) = \mathcal{O}(n \log n).

  • Space Complexity: O(n)\mathcal{O}(n), as we use a queue of size nn.

Report Article Issue

Comments: 10
hngst's avatar
Read More

Python solution

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: -x[1])
        cur_size = 0
        max_units = 0
        for num_box, unit in boxTypes:
            max_units += unit * min(truckSize - cur_size, num_box)
            cur_size += min(truckSize - cur_size, num_box)
        return max_units

10
Show 2 replies
Reply
Share
Report
lavos4life's avatar
Read More
3
Reply
Share
Report
hao_94819's avatar
Read More

Java solution:
The first I was thinking about is exactly the Array Sort approach, but I used a while loop inside the for loop to avoid the Minimum comparison. Apparently it too way to long with my solution.

        Arrays.sort(boxTypes, (a, b) -> b[1] - a [1]);
        int unitCnt = 0;
         
        for (int[] box : boxTypes){
            while (truckSize > 0 && box[0] > 0){
                unitCnt += box[1];
                box[0]--;
                truckSize--;
            }
        }
        return unitCnt;

0
Show 1 reply
Reply
Share
Report
saransh98's avatar
Read More

Using a priority queue, shouldn't the complexity be O(k*log(n)) where k is the size of the truck?

0
Reply
Share
Report
woohhan's avatar
Read More

approach 3 is basically the same as 2. but you can get O(nlogk) time complexity by deleting the element while for loop. (k is the average length of pq, in worst case it is n)
It is the same idea with https://leetcode.com/problems/kth-largest-element-in-an-array/

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[1]-b[1]);
        int size = 0;
        int totalUnits = 0;
        for (int[] box : boxTypes) {
            pq.offer(box);
            size += box[0];
            totalUnits += box[0]*box[1];
            while (size - pq.peek()[0] >= truckSize) {
                int[] top = pq.poll();
                size -= top[0];
                totalUnits -= top[0]*top[1];
            }
        }
        if (size <= truckSize) return totalUnits;
        return totalUnits - (size - truckSize)*pq.peek()[1];
    }
}

0
Reply
Share
Report
sasungrigoryan's avatar
Read More

In the complexity analysis of the 2nd approach, the additional space complexity is specified as O(1) which is wrong. The sorting step typically uses some variation of the Quicksort algorithm which adds additional space of O(logN).

0
Reply
Share
Report
neon_blue_'s avatar
Read More

I used python heap in amazon's OA2 and failed hidden cases.

0
Show 8 replies
Reply
Share
Report
venki07's avatar
Read More

C# solution

public int MaximumUnits(int[][] boxTypes, int truckSize) {        
        Array.Sort(boxTypes, (a, b) => {return b[1] - a[1];});
        int count = 0;
        
        foreach(var type in boxTypes)
        {
            int num = Math.Min(type[0], truckSize);
            count += num*type[1];            
            if(truckSize < num)
                break;
            truckSize -= num;            
        } 
        return count;
    }

0
Reply
Share
Report
pcj_terence_bhaiya's avatar
Read More

class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes = sorted(boxTypes, key=lambda x:x[1], reverse=True)
b = boxTypes
print(b)
l = len(boxTypes)
cap = 0
for i in range(l):
# truckSize = truckSize - b[i][0]
if truckSize > b[i][0]:
cap+=b[i][0]b[i][1]
truckSize = truckSize - b[i][0]
else:
cap+=truckSize
b[i][1]
break

        print(cap)
    return cap

-1
Reply
Share
Report
mohit2494's avatar
Read More

from operator import itemgetter
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
lst = sorted(boxTypes, key=itemgetter(1), reverse=True)
i,l,totalUnits, totalBoxes = 0, len(boxTypes), 0, 0
while i < l and totalBoxes < truckSize:
numBoxes, numUnits = lst[i]
print(numBoxes, numUnits)
while numBoxes>0 and totalBoxes < truckSize:
totalUnits+=numUnits
numBoxes-=1
totalBoxes+=1
i+=1
return totalUnits

-6
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/14/2021 19:02Accepted216 ms51.2 MBcpp
01/03/2021 08:12Accepted440 ms51.5 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.